Żołędzie

Limit pamięci: 64 MB

W samym środku Stubajtowego Lasu rośnie Rozłożysty Dąb. W dziupli tego dębu mieszka wiewiórka Basia, która każdego dnia wykonuje osobliwą wędrówkę po Lesie. Zaczyna u podstawy dębu z pyszczkiem skierowanym na północ i w każdej jednostce czasu wykonuje ruch. Ruch wygląda następująco: jeżeli w miejscu, w którym stoi Basia znajduje się żołądź, wiewiórka zabiera go, obraca się o w prawo i idzie jeden metr do przodu. Jeżeli natomiast żołędzia nie było, Basia upuszcza w tym miejscu żołądź, obraca się o w lewo i idzie metr do przodu. Twoim zadaniem jest policzyć ile żołędzi będzie leżało na ziemi po upływie jednostek czasu.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita () oznaczająca ile żołędzi znajdowało się na ziemi w chwili 0. Kolejne wierszy opisuje żołędzie: każdy zawiera dwie liczby całkowite () oddzielone pojedynczym odstępem. Oznacza to, że w odległości metrów na wschód i metrów na południe od podstawy dębu znajduje się żołądź. W dowolnym punkcie znajduje się co najwyżej jeden żołądź. W ostatnim wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę jednostek czasu, przez które wędrowała po Lesie wiewiórka.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą liczbę żołędzi leżących na ziemi po jednostkach czasu. Można założyć, że Basia posiada nieograniczoną liczbę żołędzi.

Przykład

Dla danych wejściowych:

2
0 0
-2 1
8

poprawną odpowiedzią jest:

6

Autor zadania: Tomasz Idziaszek.